/**
 * Project Name:javaBaseReview
 * Package Name:com.xuwei.base.graph
 * author:David
 * Date:2015年8月21日上午11:45:58
 * Copyright (c) 2015, xw123box@126.com All Rights Reserved.
 *
 */
package com.xuwei.base.graph;

import com.xuwei.base.link.Node;
import com.xuwei.base.queue.Queue;
import com.xuwei.base.queue.QueueLink;
import com.xuwei.base.stack.Stack;
import com.xuwei.base.stack.StackSLinked;
import com.xuwei.ext.exception.UnsupportedOpertation;

/**
 * @author David
 * @since 2015年8月21日 上午11:45:58
 * @version 
 * @since JDK 1.6
 */
public abstract class AbstractGraph implements Graph {
	/*图的顶点集合*/
	private LinkListDLNode vertexs=new LinkListDLNode();
	/*图的边集合*/
	private LinkListDLNode edges=new LinkListDLNode();

	@Override
	public int getType() {
		return 0;
	}

	@Override
	public int getVexNum() {
		return vertexs.getSize();
	}

	@Override
	public int getEdgeNum() {
		return edges.getSize();
	}

	@Override
	public Iterator getVertex() {
		//得到顶点表LinkList的迭代器
		LinkListIterator iterator=new LinkListIterator(vertexs);
		return iterator;
	}

	@Override
	public Iterator getEdge() {
		//得到边表LinkList的迭代器
		LinkListIterator iterator=new LinkListIterator(edges);
		return iterator;
	}

	@Override
	public void remove(Vertex v) {
		//删除与顶点相关的边
		LinkList _edges = v.getAdjacentEdges();
		if(Graph.DirectedGraph == getType()){
			LinkList edges2 = v.getReAdjacentEdges();
			_edges.addAll(edges2);
		}
		if(!_edges.isEmpty()){
			Iterator it = _edges.elements();
			for(it.first();!it.isDone();it.next()){
				Edge _edge = (Edge)it.currentItem();
				edges.remove(_edge.getEdgePosition());
			}
		}
		//删除顶点
		vertexs.remove(v.getVexPosition());
	}

	@Override
	public void remove(Edge e) {
		edges.remove(e.getEdgePosition());
	}

	@Override
	public Node insert(Vertex v) {
		return vertexs.insertLast(v);
	}

	@Override
	public Node insert(Edge e) {
		return edges.insertLast(e);
	}

	@Override
	public boolean areAdjacent(Vertex u, Vertex v) {
		return false;
	}

	@Override
	public Edge edgeFromTo(Vertex u, Vertex v) {
		return null;
	}

	@Override
	public Iterator adjVertexs(Vertex u) {
		return null;
	}

	@Override
	public Iterator DFSTraverse(Vertex v) {
		LinkList traverseSeq=new LinkListDLNode();
		resetVexStatus();
//		DFSRecursion(v,traverseSeq);
		DFS(v, traverseSeq);
		/**从图未曾访问的其他顶点重新搜索*/
		Iterator it=getVertex();
		for(it.first();!it.isDone();it.next()){
			Vertex u=(Vertex)it.currentItem();
			if(!u.isVisited()){
//				DFSRecursion(u, traverseSeq);
				DFS(v, traverseSeq);
			}
		}
		return traverseSeq.elements();
	}
	
	/**
	 * 从顶点v出发深度优先搜索
	 * @param v
	 * @param traverseSeq
	 */
	private void DFSRecursion(Vertex v, LinkList list) {
		v.setToVisited();//设置顶点v为已访问
		list.insertLast(v);//访问顶点v
		Iterator it=adjVertexs(v);//取得顶点v的所有邻接点
		for(it.first();!it.isDone();it.next()){
			Vertex u=(Vertex)it.currentItem();
			if(!u.isVisited()){
				DFSRecursion(u, list);
				DFS(u, list);
			}
		}
	}

	/**
	 * 重置顶点状态
	 */
	protected void resetVexStatus() {
		Iterator it=getVertex();
		for(it.first();!it.isDone();it.next()){
			Vertex v=(Vertex)it.currentItem();
			v.resetStatus();
		}
	}
	
	/**
	 * 从顶点v出发深度优先搜索的非递归算法
	 * @param v
	 * @param list
	 */
	private void DFS(Vertex v, LinkList list){
		Stack s = new StackSLinked();
		s.push(v);
		while(!s.isEmpty()){
			Vertex u = (Vertex)s.pop();//取栈顶元素
			if(!u.isVisited()){    //如果没有访问过
				u.setToVisited();  //访问之
				list.insertLast(u);
				Iterator it = adjVertexs(u);//未访问的邻接点入栈
				for(it.first();!it.isDone();it.next()){
					Vertex adj = (Vertex)it.currentItem();
					if(!adj.isVisited()){
						s.push(adj);
					}
				}//for
			}//if
		}//while
	}
	
	@Override
	public Iterator BFSTraverse(Vertex v) {
		LinkList traverseSeq=new LinkListDLNode();//遍历结果
		resetVexStatus();//重置顶点状态
		BFS(v,traverseSeq);//从v点出发广度优先搜索
		Iterator it=getVertex();//从图中未访问的顶点重新搜索
		for(it.first();!it.isDone();it.next()){
			Vertex u=(Vertex) it.currentItem();
			if(!u.isVisited()){
				BFS(u,traverseSeq);
			}
		}
		return traverseSeq.elements();
	}

	/**
	 * @param v
	 * @param list
	 */
	private void BFS(Vertex v, LinkList list) {
		Queue q=new QueueLink();
		v.setToVisited();//访问顶点v
		list.insertLast(v);
		q.enqueue(v); //顶点v入队
		while(!q.isEmpty()){
			Vertex u=(Vertex)q.dequeue();//队首元素出队
			Iterator it=adjVertexs(u);//访问其未曾访问的邻接点，并入队
			for(it.first();!it.isDone();it.next()){
				Vertex adj=(Vertex) it.currentItem();
				if(!adj.isVisited()){
					adj.setToVisited();
					list.insertLast(adj);
					q.enqueue(adj);
				}//if
			}//for
		}//while
	}

	@Override
	public Iterator shortestPath(Vertex v) {//【采用Dijkstra算法】
		LinkList sPath = new LinkListDLNode();//所有的最短路径序列
		resetVexStatus();//重置图中各顶点的状态信息
		//初始化，将v到各顶点的最短距离初始化为由v直接可达的距离
		Iterator it = getVertex();
		for(it.first();!it.isDone();it.next()){
			Vertex u = (Vertex)it.currentItem();
			int weight = Integer.MAX_VALUE;
			Edge e = edgeFromTo(v, u);
			if(e!=null){
				weight = e.getWeight();
			}
			if(u==v){
				weight = 0;
			}
			Path p = new Path(weight, v, u);
			setPath(u, p);
		}
		v.setToVisited();//顶点进入集合S
		sPath.insertLast(getPath(v));//求得的最短路径进入链接表
		for(int i=1;i<getVexNum();i++){//进行|V|-1次循环找到|V|-1条最短路径
			Vertex k = selectMin(it);   //找V-S中distance最小的点k
			k.setToVisited();            //顶点k加入S
			sPath.insertLast(getPath(k));//求得的最短路径进入链接表
			int distK = getDistance(k);  //修改V-S中顶点当前最短路径
			Iterator adjIt = adjVertexs(k);//取出k的所有邻接点
			for(adjIt.first();!adjIt.isDone();adjIt.next()){
				Vertex adjV = (Vertex)adjIt.currentItem();//k的邻接点adjV
				Edge e = edgeFromTo(k, adjV);
				//发现更短的路径
				if((long)distK+(long)e.getWeight()<(long)getDistance(adjV)){
					setDistance(adjV, distK+e.getWeight());
					amendPathInfo(k, adjV);//以k的路径信息修改adjV的路径信息
				}
			}//for
		}//for
		return sPath.elements();
	}

	/**
	 * @param k
	 * @param adjV
	 */
	protected void amendPathInfo(Vertex k, Vertex adjV) {
		Path p = (Path)adjV.getAppObj();
		p.clearPathInfo();
		p.addPathInfo(k);
		adjV.setAppObj(p);
	}

	/**
	 * 在顶点集合中选择路径距离最小的
	 * @param it
	 * @return Vertex
	 */
	protected Vertex selectMin(Iterator it) {
		Vertex min = null;
		for(it.first();!it.isDone();it.next()){
			Vertex v = (Vertex)it.currentItem();
			if(!v.isVisited()){
				min = v;break;
			}
		}
		for(;!it.isDone();it.next()){
			Vertex v = (Vertex)it.currentItem();
			if(!v.isVisited()&&getDistance(v)<getDistance(min)){
				min = v;
			}
		}
		return min;
	}

	@Override
	public void generateMST() throws UnsupportedOpertation {
		
	}

	//查找轻边在V-S中的顶点
	protected Vertex selectMinVertex(Iterator it){
		Vertex min = null;
		for(it.first();!it.isDone();it.next()){
			Vertex v = (Vertex)it.currentItem();
			if(!v.isVisited()){
				min = v;
				break;
			}
		}
		for(;!it.isDone();it.next()){
			Vertex v = (Vertex)it.currentItem();
			if(!v.isVisited()&&getCrossWeight(v)<getCrossWeight(min)){
				min = v;
			}
		}
		return min;
	}
	
	
	/**
	 * 获取到达顶点v的最小横切边权值
	 * @param v
	 * @return int
	 */
	protected int getCrossWeight(Vertex v){
		if(getCrossEdge(v)!=null){
			return getCrossEdge(v).getWeight();
		}else{
			return Integer.MAX_VALUE;
		}
	}
	
	/**
	 * 获取到达顶点v的最小横切边
	 * @param v
	 * @return Edge
	 */
	protected Edge getCrossEdge(Vertex v){
		return (Edge)v.getAppObj();
	}
	
	/**
	 * 设置到达顶点v的最小横切边
	 * @param v
	 * @param u
	 */
	protected void setCrossEdge(Vertex v, Edge e) {
		v.setAppObj(e);
	}

	/**
	 * 重置途中各边的类型信息
	 */
	protected void resetEdgeType() {
		Iterator it = getEdge();
		for(it.first();!it.isDone();it.next()){
			Edge e = (Edge)it.currentItem();
			e.resetType();
		}
		
	}

	@Override
	public Iterator toplogicalSort() throws UnsupportedOpertation {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public void criticalPath() throws UnsupportedOpertation {
		// TODO Auto-generated method stub

	}
	
	/**
	 * 取顶点v的当前最短距离
	 * @param v
	 * @return
	 */
	protected int getDistance(Vertex v){
		return ((Path)v.getAppObj()).getDistance();
	}
	/**
	 * 设置顶点v的当前最短距离
	 * @param v
	 * @param distance
	 */
	protected void setDistance(Vertex v, int distance){
		((Path)v.getAppObj()).setDistance(distance);
	}
	/**
	 * 取顶点v的当前最短距离
	 * @param v
	 * @return
	 */
	protected Path getPath(Vertex v){
		return (Path)v.getAppObj();
	}
	/**
	 * 设置顶点v的当前最短路径
	 * @param v
	 * @param p
	 */
	protected void setPath(Vertex v, Path p){
		v.setAppObj(p);
	}
	

}
